import itertools
import random

import itertools
import random


class KOPT:
    """
    K-Opt算法类，用于解决旅行商问题（TSP）等路径优化问题。
    """

    @staticmethod
    def kopt(obj_func, path, k):
        """
        执行k-opt局部搜索，寻找更优的路径。

        参数:
        obj_func (function): 目标函数，用于计算路径的代价。
        path (list): 当前路径，表示城市序列。
        k (int): k-opt中的k值，表示反转的子路径长度。

        返回:
        tuple: (最优路径, 最优路径的代价)
        """
        best_path = path[:]
        best_val = obj_func(path)
        n = len(path)

        for comb in itertools.combinations(range(n), k):
            # 反转子路径
            start, end = comb[0], comb[-1] + 1
            new_path = path[:start] + list(reversed(path[start:end])) + path[end:]
            new_val = obj_func(new_path)

            if new_val < best_val:
                best_path = new_path
                best_val = new_val

        return best_path, best_val

    @staticmethod
    def generate_rand_init_sols(obj_func, city_dict, num_sols):
        """
        生成随机初始解。

        参数:
        obj_func (function): 目标函数，用于计算路径的代价。
        city_dict (dict): 城市及其决策变量的字典。
        num_sols (int): 生成的初始解的数量。

        返回:
        list: 初始解的列表，每个解是一个(路径, 路径代价)的元组。
        """
        cities = list(city_dict.keys())
        solutions = []
        for _ in range(num_sols):
            init_guess = random.sample(cities, len(cities))
            solutions.append((init_guess, obj_func(init_guess)))
        return solutions

    @staticmethod
    def minimize(obj_func, city_dict, init_guess=None, max_k=-1):
        """
        使用k-opt算法最小化路径代价。

        参数:
        obj_func (function): 目标函数，用于计算路径的代价。
        city_dict (dict): 城市及其决策变量的字典。
        init_guess (list, optional): 初始路径猜测，默认为None。
        max_k (int, optional): k-opt中的最大k值，默认为-1（自动计算）。

        返回:
        tuple: (最优路径, 最优路径的代价)
        """
        num_rand_sols = 6 if init_guess is None else 5
        all_sols = []

        # 处理初始猜测
        if init_guess is not None:
            if isinstance(init_guess, str):
                init_guess = list(init_guess)
            cities = list(city_dict.keys())
            while len(set(init_guess)) != len(init_guess) or sorted(init_guess) != sorted(cities):
                init_guess = random.sample(cities, len(cities))
            all_sols.append((init_guess, obj_func(init_guess)))

        # 生成额外的随机解
        all_sols.extend(KOPT.generate_rand_init_sols(obj_func, city_dict, num_rand_sols))

        # 选择当前最优解
        best_sol = min(all_sols, key=lambda x: x[1])
        best_path = best_sol[0]
        best_val = best_sol[1]

        # 自动计算max_k
        if max_k == -1:
            max_k = len(best_path) - 1

        # 执行k-opt搜索
        current_path = best_path
        for k in range(2, max_k + 1):
            current_path, current_val = KOPT.kopt(obj_func, current_path, k)
            if current_val < best_val:
                best_val = current_val
                best_path = current_path

        return best_path, best_val


# 中文文档
"""
KOPT 类用于实现 K-Opt 算法，该算法是一种局部搜索方法，常用于解决旅行商问题（TSP）等路径优化问题。

方法:
1. kopt(obj_func, path, k): 执行 k-opt 局部搜索，寻找更优的路径。
2. generate_rand_init_sols(obj_func, city_dict, num_sols): 生成随机初始解。
3. minimize(obj_func, city_dict, init_guess=None, max_k=-1): 使用 k-opt 算法最小化路径代价。

参数说明:
- obj_func: 目标函数，用于计算路径的代价。
- city_dict: 城市及其决策变量的字典。
- init_guess: 初始路径猜测，可选参数，默认为 None。
- max_k: k-opt 中的最大 k 值，可选参数，默认为 -1（自动计算）。

返回值:
- 返回最优路径及其代价的元组 (最优路径, 最优路径的代价)。
"""


def ObjFuc(path):
    # 计算路径的总距离
    total_distance = 0
    n = len(path)
    for i in range(n):
        city1 = dict_city[path[i]]
        city2 = dict_city[path[(i + 1) % n]]
        total_distance += ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5
    return total_distance


if __name__ == '__main__':
    random.seed(42)
    # 生成两个长度为26的随机数列表
    List_x = [round(random.uniform(0, 30), 2) for _ in range(50)]
    List_y = [round(random.uniform(0, 30), 2) for _ in range(50)]

    dict_city = {chr(ord('A') + i): (List_x[i], List_y[i]) for i in range(50)}

    best_path, best_fval  = KOPT.minimize(ObjFuc, dict_city, None, max_k=4)

    # 打印最好的解
    print("Best Path:", best_path)
    print("Total Distance:", best_fval)